package com.lsa.iview.ama.count_x_in_sorted_arr;

import java.util.Comparator;

public class CountExInSortedArray {
	public static void main(String[] args) {
	}
	
	public static <T> int count(T[] arr, T x, Comparator<T> comp) {
		int left = pointLeftBound(arr, x, comp);
		if (left > -1) {
			int right = pointRightBound(arr, x, comp);
			return right - left + 1;
		}
		
		return -1;
	}
	
	static <T> int pointLeftBound(T[] arr, T x, Comparator<T> comp) {
		int left = 0;
		int right = arr.length - 1;
		
		while(left <= right) {
			int idx = (left+right)>>1;
		
			int cmp = compareForLeftBound(arr, x, idx, comp);
			if (cmp == 0) {
				return idx;
			}
			else if (cmp < 0) {
				left = idx + 1;
			}
			else {
				right = idx - 1;
			}
		}
		return -(left+1);
	}
	
	static <T> int pointRightBound(T[] arr, T x, Comparator<T> comp) {
		int left = 0;
		int right = arr.length - 1;
		
		while(left <= right) {
			int idx = (left+right)>>1;
		
			int cmp = compareForRightBound(arr, x, idx, comp);
			if (cmp == 0) {
				return idx;
			}
			else if (cmp < 0) {
				left = idx + 1;
			}
			else {
				right = idx - 1;
			}
		}
		return -(left+1);
	}
	
	static <T> int compareForLeftBound(T[] arr, T x, int idx, Comparator<T> comp) {
		if (comp.compare(arr[idx], x) > 0 ) {
			return 1;
		}
		else if (comp.compare(arr[idx], x) < 0 ) {
			return -1;
		}
		else {
			if (idx > 0) {
				if (comp.compare(arr[idx-1], arr[idx]) != 0) {
					return 0;
				}
				else {
					return 1;
				}
			}
			else {
				return 0;
			}
		}
	}
	
	static <T> int compareForRightBound(T[] arr, T x, int idx, Comparator<T> comp) {
		if (comp.compare(arr[idx], x) > 0 ) {
			return 1;
		}
		else if (comp.compare(arr[idx], x) < 0 ) {
			return -1;
		}
		else {
			if (idx < arr.length - 1) {
				if (comp.compare(arr[idx], arr[idx+1]) != 0) {
					return 0;
				}
				else {
					return -1;
				}
			}
			else {
				return 0;
			}
		}
	}
	
	/**
	 * Just to refresh myself :)
	 * @param arr
	 * @param x
	 * @param comp
	 * @return
	 */
	static <T> int binarySearch(T[] arr, T x, Comparator<T> comp) {
		int left = 0;
		int right = arr.length - 1;
		
		while(left <= right) {
			int idx = (left+right)>>1;
			int cmp = comp.compare(arr[idx],x);
			if (cmp == 0) {
				return idx;
			}
			else if (cmp < 0) {
				left = idx + 1;
			}
			else {
				right = idx - 1;
			}
		}
		
		return -(left+1);
	}
}
